// https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof/submissions/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    // 从根节点判断是不是子结构
    bool helper(TreeNode* A, TreeNode* B) {
        if (!B) return true; // B已经访问完了，确定是A的子结构
        if (!A || A->val != B->val) return false;
        return helper(A->left, B->left) && helper(A->right, B->right);
    }
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if (!A || !B) return false;
        return helper(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B); // 从根节点判断B是不是A的子结构，如果不是在分别从左右两个子树判断
    }
};